class Solution {
public:
    vector<int> _grayCode(int n) {
        if (n == 1) {
            // 当要生成的格雷码只有一位的时候直接返回0
            return {0, 1};
        }
        vector<int> prevcode = _grayCode(n - 1); // 获取n-1位的格雷码
        // 构造第n位的格雷码
        // 首先就是将前n-1位格雷码的前面加上一个0
        //  前半部分：在 n-1 位格雷码前面加 "0"
        vector<int> grayCode;
        for (int code : prevcode) {
            grayCode.push_back(
                code); // 直接添加前半部分，因为是int不需要手动增加前置0
        }

        // 后半部分：在 n-1 位格雷码逆序后前面加 "1"
        reverse(prevcode.begin(), prevcode.end()); // 逆序
        for (int code : prevcode) {
            grayCode.push_back(code | (1 << (n - 1))); // 在最高位加 1
        }

        return grayCode;
    }
    vector<int> grayCode(int n) {
        // //
        // 这道题目可以使用递归的方法和迭代的方法解决，要解决这道题目首先要理解什么是格雷编码，格雷编码是一组数据
        // //
        // 但是相邻两个数之间二进制只相差一位，而首位和尾位也是符合这个要求的。
        // // 第一种递归方法:
        // // 递归法的核心思想：
        // // 基本情况：当 n=1 时，格雷码只有两种可能：["0", "1"]。
        // // 递归步骤：
        // // 生成 n−1 位的格雷码。
        // // 将 n−1 位的格雷码前面加 0，得到前半部分。
        // // 将 n−1 位的格雷码逆序后前面加 1，得到后半部分。
        // // 合并前半部分和后半部分，得到 n 位的格雷码。
        // // 这个递归能够完成的核心是格雷码的对称性：
        // // n 位格雷码的前半部分是在 n−1 位格雷码前面加 0。
        // // n 位格雷码的后半部分是在 n−1 位格雷码的逆序前面加 1。
        // // 在递归的时候将n-1位的格雷码储存起来然后使用对称性即可完成这道题目
        // vector<int> ret = _grayCode(n);
        // return ret;
        // 第二种解法：格雷码的公式
        // 通过公式生成格雷码
        vector<int> grayCode;

        // 遍历从 0 到 2^n - 1 的所有数字
        for (int i = 0; i < (1 << n); i++) {
            // 计算格雷码：G(i) = i ^ (i >> 1)
            int gray = i ^ (i >> 1);

            // 将格雷码直接添加到结果中
            grayCode.push_back(gray);
        }

        return grayCode;
    }
};